package com.lizk.sort;

import com.lizk.heap.MaxHeap;
import com.lizk.heap.MaxHeapFromZero;

/**
 * @author lizhikui
 * @date 2020/2/9 14:49
 */
public class MaxHeapSort {
    /**
     * 创建一个最大堆，然后复制回原数组的正确位置
     * @param array
     * @return
     */
    public static Integer []  sort (Integer[] array){
        MaxHeap maxHeap = new MaxHeap(array.length);
        /*
        最大堆排序，是nlogn时间复杂度的排序算法，
        这里有一个时间复杂度为n循环，循环里嵌套的insertValue和takeValue都是logn级别的算法
         */
        for (int value : array) {
            maxHeap.insertValue(value);
        }
        for (int i = array.length - 1; i >= 0 ; i--) {
            int v = maxHeap.takeValue();
            array[i] = v;
        }
        return array;
    }

    public static Integer []  sort2 (Integer[] array){
        MaxHeapFromZero maxHeap = new MaxHeapFromZero(array);
        /*
        最大堆排序，是nlogn时间复杂度的排序算法，
        这里有一个时间复杂度为n循环，循环里嵌套的insertValue和takeValue都是logn级别的算法
         */
        for (int i = array.length - 1; i >= 0 ; i--) {
            int i1 = maxHeap.takeValue();
            array[i] = i1;
        }
        return array;
    }

}
